/*
前序序列化:
  类似前序遍历: 访问到节点，序列化为val+'!'(分隔符), 如果访问到null，返回'#'+'!'
层序序列化:
  层序遍历的过程: 根节点入队，队列不为空，出队打印，然后入队left,right
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  if (!root) {
    return '#!'
  }
  let str = ''
  str += root.val + '!'
  str += serialize(root.left)
  str += serialize(root.right)
  return str
}

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serializeByLevel = function (root) {
  let str = ''
  const queue = []
  queue.push(root)
  while (queue.length) {
    const node = queue.shift()
    if (node) {
      str += node.val + '!'
      queue.push(node.left)
      queue.push(node.right)
    } else {
      str += '#!'
    }
  }
  return str
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const nodes = data.split('!')
  return genTree(nodes)
}

/**
 * generate tree using nodes
 * @param {string[]} nodes
 */
function genTree (nodes) {
  const nodeVal = nodes.shift()
  let newNode
  if (nodeVal === '#') {
    return null
  } else {
    newNode = new TreeNode(parseInt(nodeVal))
  }
  newNode.left = genTree(nodes)
  newNode.right = genTree(nodes)
  return newNode
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserializeByLevel = function (data) {
  const nodes = data.split('!')
  const queue = []
  const headVal = nodes.shift()
  if (headVal === '#') {
    return null
  } else {
    const head = new TreeNode(parseInt(headVal))
    queue.push(head)
    while (queue.length) {
      const node = queue.shift()
      if (node) {
        let nodeVal = nodes.shift()
        node.left = nodeVal === '#' ? null : new TreeNode(parseInt(nodeVal))
        queue.push(node.left)
        nodeVal = nodes.shift()
        node.right = nodeVal === '#' ? null : new TreeNode(parseInt(nodeVal))
        queue.push(node.right)
      }
    }
    return head
  }
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
